package Q704

class Main {

}

fun main(){
    var arr = intArrayOf(-1,0,3,5,9,12)
    var target = 9
    println(Solution().search(arr, target))
}

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var left = 0
        var right = nums.size
        while(left <= right){
            val mid = ((right - left) ushr 1) + left
            when{
                nums[mid] == target -> return mid
                nums[mid] > target -> right = mid - 1
                else -> left = mid + 1
            }
        }
        return -1
    }
}

